This invention relates to computer systems and, more particularly, to identifying free registers in a computer.
During the execution of a computer program, a register xe2x80x9cRxe2x80x9d is called xe2x80x9cfreexe2x80x9d if, for all possible execution paths of a program from that particular point forward, the content of R is always written before being read. If register R is not free then it is said to be in use.
Knowing whether a register is free or in use is important for many reasons. For example, when calling subroutines, if the free registers are known, then the contents of the free registers do not have to be saved upon entry to the subroutine and restored upon return from the subroutine. This saves processing time which would otherwise be required to store and restore data to/from memory in order to ensure that the use of a register while executing the subroutine does not interfere with subsequent program execution. Thus, a determination of which registers are free at various points while executing a program is typically performed during program compiling and is an important aspect in compiler design in the context of assignment of registers.
A conventional method of locating free registers during compiling is illustrated in FIG. 1. The first step in this method is to construct a complete flow graph. Next, for each register the edges of the graph are explored backwards, starting from each Read instruction from that register and stopping at all Write instructions to that register. At each point that is reached before a Write is reached, that particular register is marked as xe2x80x9cin-usexe2x80x9d or not free.
For example, in FIG. 1, for register R1 the flow graph is examined from the Read 1 at 50. Working backwards from the Read 1 at 50, each execution path reaches a Write at 52 before a point of interest 55 is reached. Therefore, register R1 is a free register at 55. For register R2 the flow graph is also examined backwards from each Read 2 statement. From the Read 2 at 54, the search reaches point 55 before a Write is reached. Therefore, register R2 is not a free register at 55.
This type of search requires analysis of the entire program and sometimes even with an entire code analysis, the system cannot make complete determinations. This is because jumps and branches within the program may require the searching algorithm to make pessimistic assumptions regarding the status of a particular register. Further, this type of search for free registers requires an amount of time which makes its use impractical during program execution.
Free registers are also required in order to implement a software xe2x80x9cpatch.xe2x80x9d A program may require a software patch to replace small portions of the original executable code with new code. The patch may be required for debugging the program, instrumentation, architecture emulation, or other reasons which are well known to those skilled in the art.
For example, in situations where an upgraded program is being run on an existing computer architecture that does not include upgraded hardware, the upgraded program may have instructions which are not executable on the older architecture. To correct this problem, a patch that emulates the upgraded hardware is inserted into the program.
When modules of a program are mapped to memory, word or page alignment of the modules may result in xe2x80x9cfree spacexe2x80x9d between aligned modules. Prior art FIG. 2 illustrates a typical program stored in memory. The program includes four modules 205-220, with free space 225-240 located between the modules. A patch can be inserted into the free space during linking or loading, or while the program is executing.
With reference to prior art FIG. 3, new source code 300 represents the patch. A compiler 310 compiles the patch and sends the compiled code to a linker 320. The linker 320 then links the compiled patch code with original program executable code 330 so that the processor can execute the program patch. The linker 320 may also be coupled to various libraries 340 that contain previously compiled code. The details of linking the patched code with the executable code are well known by those skilled in the art and accordingly will not be further described herein.
Conventionally, when a patch is needed for a program, the contents of all required registers are saved to memory and then restored after the patch is executed. This may result in a serious performance penalty during program execution. For example, the time spent storing and restoring the contents of the registers to/from memory may slow the operation of the program to the point where the program execution is unacceptable. This is particularly true in cases where the patch is executed in a loop with many iterations.
Prior art FIG. 4 illustrates a conventional patch executed within a program. At the step labeled 10, the program is executing. At step 12, a jump to the patch occurs. The program proceeds at step 14 to save the contents of required registers to memory or stack. In step 16, the patch is executed. Upon completion of the patch execution, the program restores the registers as indicated at step 18 and jumps back to the program execution at step 20. In other implementations, a patch can directly be inserted in the executable code.
In view of the above, a need exists for an improved technique to locate free registers within a program.
Accordingly, it is an object of the invention to locate free registers in an efficient manner. The free registers can then be utilized for various purposes, such as a software patch.
Another object of the invention is to execute a software patch without saving and restoring the content registers to memory.
A further object of the invention is to dynamically locate free registers while a program is executing without undue delays.
Yet another object of the invention is to reduce the number of instances of the same patch stored in memory.
Other objects and advantages of the present invention will become readily apparent to those skilled in this art from the following detailed description. The embodiments shown and described provide illustration of the best mode contemplated for carrying out the invention. The invention is capable of modifications in various obvious respects, all without departing from the invention. Accordingly, the drawings are to be regarded as illustrative in nature, and not as restrictive.
To achieve the foregoing and other object and advantages, the present invention provides a technique for locating free registers within a plurality of registers. In accordance with the invention, a point of interest within an execution flow of a program, e.g., a point at which a jump to a patch will be eventually inserted, is selected. A search is performed from the point of interest to locate registers that will be written prior to being read, subsequent to, i.e., downstream of, the point of interest in the program""s execution flow. The search is performed by using a flow graph constructed by analyzing the execution flow.
In accordance with other aspects of the invention, the search associated with a particular register is terminated when the particular register is determined to be in use. The identity of the located free registers may be stored for later use by, for example, a patch. The patch may then be executed by writing data in the identified free registers. Additionally, saved search results may be utilized by other searches that may overlap the saved results. Further, if desired, the flow graph may be searched for more than one free register at the same time or searched from more than one point of interest at the same time.
In further aspects of the invention, a timer may be started when the search for free registers begins, and the search can be terminated when the timer times out.
According to one embodiment of the invention, a computer system performs the steps for identifying free registers. The computer system includes a processor executing sequences of instructions contained in a computer-readable medium. This medium may, for example, be dynamic random access memory (DRAM). Alternatively, the medium could be any other data storage device that would be known to one of ordinary skill in the art.